

a = 156853895847604116708242664263151514811095704969640303272039451331791888050995073274981545693518063639560286348739938318495685137088495867703518198511200409009953879436648706837731243061114851474801565873584183542649886358523850682697732574913523360866915083642887238043256280849100274825940626065115676325169
c = 3459715117165130065996389169943285249501133832272446001239391765859259811270526185228996906338576254353123756173289118671028939933226544773197852424767051933844004667155191851195814295922794480300237399956789038592856532530692732011427288405114650955620859282144504446058845961744702163836107847961388150810
e = 65537
import gmpy2
import libnum

p1=libnum.nroot(a,2)
while a%p1!=0:
    p1=gmpy2.next_prime(p1)
q=int(p1)
p=a//q
print(a==p*q)
phi=(p-1)*(q-1)
d=libnum.invmod(e,phi)
m=pow(c,d,a)
print(m)

m1=m*libnum.invmod(-1,p)%p
for i in range(p,q):
    print(i)
    m=m*i%a
m2=m*libnum.invmod(-1,q)%q

mm=libnum.solve_crt([m1,m2],[p,q])
print(mm)
print(libnum.n2s(int(mm)))




